package main

import "fmt"

/**
 * 插入排序
 */
func insertionSort(a []int) []int {
	// [3,5,6,8][1,8,0,3,9,2]
	//        |  |
	//        j  i
	for i := 0; i < len(a); i++ {
		e := a[i]
		j := i - 1
		for j >= 0 {
			if e < a[j] {
				a[j+1] = a[j]
			} else {
				break
			}
			j--
		}
		a[j+1] = e
	}
	return a
}

func main() {
	a1 := [...]int{}
	a2 := [...]int{3}
	a3 := [...]int{1, 2, 3}
	a4 := [...]int{1, 3, 2}
	a5 := [...]int{2, 1, 3}
	a6 := [...]int{2, 3, 1}
	a7 := [...]int{3, 1, 2}
	a8 := [...]int{3, 2, 1}
	a9 := [...]int{3, 1, 1, 1}
	a10 := [...]int{1, 1, 1, 1}
	a11 := [...]int{1, 9, 5, 2, 9, 1, 5, -5, 2, 9, 5, 1, 9, 2, 1}

	fmt.Printf("a1 = %v\n", a1)
	fmt.Printf("a2 = %v\n", a2)
	fmt.Printf("a3 = %v\n", a3)
	fmt.Printf("a4 = %v\n", a4)
	fmt.Printf("a5 = %v\n", a5)
	fmt.Printf("a6 = %v\n", a6)
	fmt.Printf("a7 = %v\n", a7)
	fmt.Printf("a8 = %v\n", a8)
	fmt.Printf("a9 = %v\n", a9)
	fmt.Printf("a10 = %v\n", a10)
	fmt.Printf("a11 = %v\n", a11)

	insertionSort(a1[:])
	insertionSort(a2[:])
	insertionSort(a3[:])
	insertionSort(a4[:])
	insertionSort(a5[:])
	insertionSort(a6[:])
	insertionSort(a7[:])
	insertionSort(a8[:])
	insertionSort(a9[:])
	insertionSort(a10[:])
	insertionSort(a11[:])
	fmt.Println()

	fmt.Printf("a1 = %v\n", a1)
	fmt.Printf("a2 = %v\n", a2)
	fmt.Printf("a3 = %v\n", a3)
	fmt.Printf("a4 = %v\n", a4)
	fmt.Printf("a5 = %v\n", a5)
	fmt.Printf("a6 = %v\n", a6)
	fmt.Printf("a7 = %v\n", a7)
	fmt.Printf("a8 = %v\n", a8)
	fmt.Printf("a9 = %v\n", a9)
	fmt.Printf("a10 = %v\n", a10)
	fmt.Printf("a11 = %v\n", a11)
}
